package operations;
import java.io.*;
class fileInfo {    
  static final int MAXLINECOUNT = 20000;
  DataInputStream Inputfile;
  public int maxLine;
  nodal symbol[];
  public int other[];
  int tym;
  fileInfo( String filename ) {
    symbol = new nodal [ MAXLINECOUNT+2 ];
    other  = null;
    try {
      Inputfile = new DataInputStream(
        new FileInputStream( filename));
    } catch (IOException e) {
        System.err.println("Diff can't read file " +
        filename );
        System.err.println("Error Exception was:" + e );
        System.exit(1);
    }
  }
  void alloc() {
    other  = new int[symbol.length + 2];
    tym=symbol.length + 2;
  }
};
public class DiffFile {

  final int UNREAL=Integer.MAX_VALUE;
  fileInfo oldinfo, newinfo;
  int blocklen[];

  public DiffFile() {
  }
  //need a mock to test
  public void doDiff(String oldFile, String newFile) {
    println( ">>>> Difference of file \"" + oldFile + 
      "\" and file \"" + newFile + "\".\n");
    oldinfo = new fileInfo(oldFile);
    newinfo = new fileInfo(newFile);
    try {
      inputscan( oldinfo );
      inputscan( newinfo );
    } catch (IOException e) {
      System.err.println("Read error: " + e);
    }
    blocklen = new int[ (oldinfo.maxLine>newinfo.maxLine?
      oldinfo.maxLine : newinfo.maxLine) + 2 ];
    oldinfo.alloc();
    newinfo.alloc();
    transform();
    hello();
  }
  void hello(){
	   for(int i=0;i<oldinfo.tym;i++){		   
		   if(oldinfo.other[i]<0)System.out.println("11  "+i+"   111");}}
  
  void inputscan( fileInfo pinfo ) throws IOException
  {
       String linebuffer;

       pinfo.maxLine = 0;
       while ((linebuffer = pinfo.Inputfile.readLine()) != null) {
           storeline( linebuffer, pinfo );
       }
  }

  void storeline( String linebuffer, fileInfo pinfo )
  {
       int linenum = ++pinfo.maxLine;
       if ( linenum > fileInfo.MAXLINECOUNT ) {
      System.err.println( "MAXLINECOUNT exceeded, must stop." );
      System.exit(1);
       }
       pinfo.symbol[ linenum ] = nodal.addSymbol( linebuffer, pinfo == oldinfo, linenum );       
  }
  void transform()
  {                                  
       int oldline, newline;
       int oldmax = oldinfo.maxLine + 2;
       int newmax = newinfo.maxLine + 2; 
       for (oldline=0; oldline < oldmax; oldline++ )
      oldinfo.other[oldline]= -1;
       for (newline=0; newline < newmax; newline++ )
      newinfo.other[newline]= -1;
       scanunique();
       scanafter();
       scanbefore();
       scanblocks();
  }
  void scanunique()
  {
       int oldline, newline;
       nodal psymbol;
       for( newline = 1; newline <= newinfo.maxLine; newline++ ) {
      psymbol = newinfo.symbol[ newline ];
      if ( psymbol.symbolIsUnique()) {        
           oldline = psymbol.linenum;
           newinfo.other[ newline ] = oldline; 
           oldinfo.other[ oldline ] = newline;
      }
       }
       newinfo.other[ 0 ] = 0;
       oldinfo.other[ 0 ] = 0;
       newinfo.other[ newinfo.maxLine + 1 ] = oldinfo.maxLine + 1;
       oldinfo.other[ oldinfo.maxLine + 1 ] = newinfo.maxLine + 1;
  }
  void scanafter()
  {
       int oldline, newline;

       for( newline = 0; newline <= newinfo.maxLine; newline++ ) {
      oldline = newinfo.other[ newline ];
      if ( oldline >= 0 ) { 
           for(;;) {  
          if ( ++oldline > oldinfo.maxLine   ) break; 
          if ( oldinfo.other[ oldline ] >= 0 ) break;
          if ( ++newline > newinfo.maxLine   ) break; 
          if ( newinfo.other[ newline ] >= 0 ) break;

          if ( newinfo.symbol[ newline ] !=
        oldinfo.symbol[ oldline ] ) break; 

          newinfo.other[newline] = oldline;
          oldinfo.other[oldline] = newline;
           }
      }
       }
  }
  void scanbefore()
  {
       int oldline, newline;

       for( newline = newinfo.maxLine + 1; newline > 0; newline-- ) {
      oldline = newinfo.other[ newline ];
      if ( oldline >= 0 ) {
           for(;;) {
          if ( --oldline <= 0                ) break;
          if ( oldinfo.other[ oldline ] >= 0 ) break;
          if ( --newline <= 0                ) break;
          if ( newinfo.other[ newline ] >= 0 ) break;
          if ( newinfo.symbol[ newline ] !=
        oldinfo.symbol[ oldline ] ) break;  // not same

          newinfo.other[newline] = oldline; // record a match
          oldinfo.other[oldline] = newline;
           }
      }
       }
  }
  void scanblocks()
  {
       int oldline, newline;
       int oldfront = 0;  
       int newlast = -1; 

       for( oldline = 1; oldline <= oldinfo.maxLine; oldline++ )
           blocklen[ oldline ] = 0;
       blocklen[ oldinfo.maxLine + 1 ] = UNREAL;

       for( oldline = 1; oldline <= oldinfo.maxLine; oldline++ ) {
      newline = oldinfo.other[ oldline ];
      if ( newline < 0 ) oldfront = 0; 
      else{
           if ( oldfront == 0 )         oldfront = oldline;
           if ( newline != (newlast+1)) oldfront = oldline;
           ++blocklen[ oldfront ];            
      }
      newlast = newline;
       }
  }

  public static final int
    idle = 0, delete = 1, insert = 2, movenew = 3, moveold = 4,
    same = 5, change = 6;
  int printstatus;
  boolean anyprinted;
  int printoldline, printnewline;

  public void println(String s) {
    System.out.println(s);
  }
};

class nodal{
  nodal pleft, pright;
  int linenum;

  static final int freshnode = 0,
  oldonce = 1, newonce = 2, bothonce = 3, other = 4;

  int linestate;
  String line;

  static nodal panchor = null;
  nodal( String pline)
  {
       pleft = pright = null;
       linestate = freshnode;
       line = pline;
  }
  static nodal matchsymbol( String pline )
  {
       int comparison;
       nodal pnode = panchor;
       if ( panchor == null ) return panchor = new nodal( pline);
       for(;;) {
      comparison = pnode.line.compareTo(pline);
      if ( comparison == 0 ) return pnode;

      if ( comparison < 0 ) {
           if ( pnode.pleft == null ) {
          pnode.pleft = new nodal( pline);
          return pnode.pleft;
           }
           pnode = pnode.pleft;
      }
      if ( comparison > 0 ) {
           if ( pnode.pright == null ) {
          pnode.pright = new nodal( pline);
          return pnode.pright;
           }
           pnode = pnode.pright;
      }
       }
  }
  static nodal addSymbol( String pline, boolean inoldfile, int linenum )
  {
    nodal pnode;
    pnode = matchsymbol( pline );
    if ( pnode.linestate == freshnode ) {
      pnode.linestate = inoldfile ? oldonce : newonce;
    } else {
      if (( pnode.linestate == oldonce && !inoldfile ) ||
          ( pnode.linestate == newonce &&  inoldfile )) 
           pnode.linestate = bothonce;
      else pnode.linestate = other;
    }
    if (inoldfile) pnode.linenum = linenum;
    return pnode;
  }
  boolean symbolIsUnique()
  {
    return (linestate == bothonce );
  }

  void showSymbol()
  {
    System.out.println(line);
  }
}
